#include<iostream>
using namespace std;
#include<vector>

void mergesort(vector<int>& arr,int left,int right){
    if(left >= right){
        return;
    }

    //求中间的mid
    int mid = left + (right-left)/2;
    
    //利用mid划分区间
    mergesort(arr,left,mid);
    mergesort(arr,mid+1,right);

    //开始合并数组
    int cur1 = left,cur2 =mid+1;
    int  i = 0;
    vector<int> tmp;
    tmp.resize(right-left+1);
    while(cur1<= mid && cur2<= right){
        //这一步就完成了排序加上移动下标
        tmp[i++] = arr[cur1] <= arr[cur2] ? arr[cur1++] : arr[cur2++];
    }

    while(cur1 <= mid) tmp[i++] = arr[cur1++];
    while(cur2 <= right) tmp[i++] = arr[cur2++];

    //把tmp的数据赋值给原来的数组
    for(int i = left;i <= right;i++){
        arr[i] = tmp[i-left];
    }
}
void print_sort(vector<int>& arr){
    for(auto e: arr){
        cout<<e<<" ";
    }
    cout<<endl;
}

int main(){
    vector<int> arr = {9,8,7,6,5,4,3,2,1,0};
    print_sort(arr);

    mergesort(arr,0,arr.size()-1);

    print_sort(arr);

    return 0;
}